#ifndef _BUOLA_GRAPH_FLOYD_H_
#define _BUOLA_GRAPH_FLOYD_H_

#include <buola/graph/cgraph.h>
#include <buola/algorithm/range.h>
#include <buola/functors/predicates/unary.h>
#include <boost/graph/floyd_warshall_shortest.hpp>

namespace buola { namespace graph {

template<typename tGraph,typename tWeightMap>
std::vector<std::vector<typename tWeightMap::value_type>> floyd_shortest_distances(const tGraph &pGraph,const tWeightMap &pWeight)
{
    std::vector<std::vector<typename tWeightMap::value_type>> lResult(num_vertices(pGraph),std::vector<typename tWeightMap::value_type>(num_vertices(pGraph)));
    boost::floyd_warshall_all_pairs_shortest_paths(pGraph,lResult,boost::weight_map(pWeight));
    return lResult;
}

template<typename tGraph,typename tWeightMap>
std::pair<typename tGraph::vertex_descriptor,typename tGraph::vertex_descriptor>
longest_shortest_path(const tGraph &pGraph,const tWeightMap &pWeight)
{
    auto lMatrix=floyd_shortest_distances(pGraph,pWeight);
    std::pair<typename tGraph::vertex_descriptor,typename tGraph::vertex_descriptor> lMaxPair;
    typename tWeightMap::value_type lMax=0.0;
    for(int i=0;i<lMatrix.size();i++)
    {
        fill_if(lMatrix[i],0.0,fn::equal_to(std::numeric_limits<typename tWeightMap::value_type>::max()));
        
        for(int j=0;j<lMatrix.size();j++)
        {
            if(lMatrix[i][j]>lMax)
            {
                lMax=lMatrix[i][j];
                lMaxPair.first=i;
                lMaxPair.second=j;
            }
        }
    }
    
    return lMaxPair;
}
                

/*namespace graph*/ } /*namespace buola*/ }

#endif
